package com.sheng.leetcode.year2022.month03.day04;

import org.junit.Test;


/**
 * @Date 2022/3/4 14:57
 * @author liusheng
 * 2104. 子数组范围和
 * 给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
 * 返回 nums 中 所有 子数组范围的 和 。
 * 子数组是数组中一个连续 非空 的元素序列。
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：4
 * 解释：nums 的 6 个子数组如下所示：
 * [1]，范围 = 最大 - 最小 = 1 - 1 = 0
 * [2]，范围 = 2 - 2 = 0
 * [3]，范围 = 3 - 3 = 0
 * [1,2]，范围 = 2 - 1 = 1
 * [2,3]，范围 = 3 - 2 = 1
 * [1,2,3]，范围 = 3 - 1 = 2
 * 所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4
 * 示例 2：
 *
 * 输入：nums = [1,3,3]
 * 输出：4
 * 解释：nums 的 6 个子数组如下所示：
 * [1]，范围 = 最大 - 最小 = 1 - 1 = 0
 * [3]，范围 = 3 - 3 = 0
 * [3]，范围 = 3 - 3 = 0
 * [1,3]，范围 = 3 - 1 = 2
 * [3,3]，范围 = 3 - 3 = 0
 * [1,3,3]，范围 = 3 - 1 = 2
 * 所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4
 * 示例 3：
 *
 * 输入：nums = [4,-2,-3,4,1]
 * 输出：59
 * 解释：nums 中所有子数组范围的和是 59
 *
 * 提示：
 *
 * 1 <= nums.length <= 1000
 * -109 <= nums[i] <= 109
 *
 * 进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sum-of-subarray-ranges
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode2104 {

    @Test
    public void test01(){
        int[] nums = {1, 3, 4, 2};
        //int nums[] = {1, 3, 3};
        //int nums[] = {4, -2, -3 ,4 ,1};
        System.out.println(new Solution().subArrayRanges(nums));
    }
}
class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        long ret = 0;
        for (int i = 0; i < n; i++) {
            int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
            for (int j = i; j < n; j++) {
                minVal = Math.min(minVal, nums[j]);
                maxVal = Math.max(maxVal, nums[j]);
                ret += maxVal - minVal;
            }
        }
        return ret;
    }
}

/**
 * class Solution {
 *     public long subArrayRanges(int[] nums) {
 *         int length = nums.length;
 *         int x = 0;
 *         int y = 1;
 *         //数组长度决定单个的数长度，例如3次
 *         long result = 0;
 *         while (length > 0) {
 *             //从0开始的最大循环，循环次数分别是3-2-1
 *             int l = 1;
 *             int o = y;
 *             for (int i = 0; i < length; i++) {
 *                 int[] test = new int[l];
 *                 for (int j = x, n = 0; j < o; j++, n++) {
 *                     test[n] = nums[j];
 *                 }
 *                 printNums(test);
 *                 result += Max(test) - Min(test);
 *                 o++;
 *                 l++;
 *             }
 *             y++;
 *             x++;
 *             length--;
 *         }
 *         return result;
 *     }
 *
 *     public int Max(int[] nums){
 *         int max = nums[0];
 *         for (int i = 1; i < nums.length; i++) {
 *             if (max < nums[i])
 *                 max = nums[i];
 *         }
 *         return max;
 *     }
 *
 *     public int Min(int[] nums){
 *         int min = nums[0];
 *         for (int i = 1; i < nums.length; i++) {
 *             if (min > nums[i])
 *                 min = nums[i];
 *         }
 *         return min;
 *     }
 *
 *     public void printNums(int[] nums){
 *         for (int i = 0; i < nums.length; i++) {
 *             System.out.print(nums[i] + "\t");
 *         }
 *         System.out.println();
 *     }
 *
 * }
 */

//class Solution {
//    public long subArrayRanges(int[] nums) {
//        int n = nums.length;
//        int[] minLeft = new int[n];
//        int[] minRight = new int[n];
//        int[] maxLeft = new int[n];
//        int[] maxRight = new int[n];
//        Deque<Integer> minStack = new ArrayDeque<Integer>();
//        Deque<Integer> maxStack = new ArrayDeque<Integer>();
//        for (int i = 0; i < n; i++) {
//            while (!minStack.isEmpty() && nums[minStack.peek()] > nums[i]) {
//                minStack.pop();
//            }
//            minLeft[i] = minStack.isEmpty() ? -1 : minStack.peek();
//            minStack.push(i);
//
//            // 如果 nums[maxStack.peek()] == nums[i], 那么根据定义，
//            // nums[maxStack.peek()] 逻辑上小于 nums[i]，因为 maxStack.peek() < i
//            while (!maxStack.isEmpty() && nums[maxStack.peek()] <= nums[i]) {
//                maxStack.pop();
//            }
//            maxLeft[i] = maxStack.isEmpty() ? -1 : maxStack.peek();
//            maxStack.push(i);
//        }
//        minStack.clear();
//        maxStack.clear();
//        for (int i = n - 1; i >= 0; i--) {
//            // 如果 nums[minStack.peek()] == nums[i], 那么根据定义，
//            // nums[minStack.peek()] 逻辑上大于 nums[i]，因为 minStack.peek() > i
//            while (!minStack.isEmpty() && nums[minStack.peek()] >= nums[i]) {
//                minStack.pop();
//            }
//            minRight[i] = minStack.isEmpty() ? n : minStack.peek();
//            minStack.push(i);
//
//            while (!maxStack.isEmpty() && nums[maxStack.peek()] < nums[i]) {
//                maxStack.pop();
//            }
//            maxRight[i] = maxStack.isEmpty() ? n : maxStack.peek();
//            maxStack.push(i);
//        }
//
//        long sumMax = 0, sumMin = 0;
//        for (int i = 0; i < n; i++) {
//            sumMax += (long) (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
//            sumMin += (long) (minRight[i] - i) * (i - minLeft[i]) * nums[i];
//        }
//        return sumMax - sumMin;
//    }
//}

